home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / pers_tre.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  5.0 KB  |  239 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  pers_tree.h
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17.  
  18. #ifndef PERS_TREE_H
  19. #define PERS_TREE_H
  20.  
  21. #include <LEDA/basic.h>
  22. #include <LEDA/list.h>
  23.  
  24. typedef void (*DRAW_NODE_FCT)(double,double,void*);
  25. typedef void (*DRAW_EDGE_FCT)(double,double,double,double);
  26.  
  27. /* implementation of a node of the ephemeral red-black tree of a specific
  28.  * persistent  node, where the colors of that persistent node through the
  29.  * various versions can be found
  30.  */
  31. class NODE;
  32. class C_NODE;
  33. class F_NODE;
  34. class VER_NODE;
  35.  
  36. typedef list_item version;
  37.  
  38.  
  39. class C_NODE
  40. {
  41.   friend class pers_rb_tree;
  42.  
  43.   version vers_stamp;
  44.   C_NODE* c_link[3];
  45.   int c_right;
  46.   int c_color;
  47.   int col_value;
  48.  
  49.   OPERATOR_NEW(7)
  50.   OPERATOR_DEL(7)
  51. };
  52.  
  53. /* implementation of a node of the  ephemeral red-black tree of a specific
  54.  * persistent node, where the children of that persistent node through the
  55.  * various versions can be found
  56.  */
  57.  
  58. class F_NODE
  59. {
  60.   friend class pers_rb_tree;
  61.  
  62.   version ver_stamp;
  63.   F_NODE* f_link[3];
  64.   int f_right;
  65.   int f_color;
  66.   NODE* poin_value;
  67.  
  68.   OPERATOR_NEW(8)
  69.   OPERATOR_DEL(8)
  70. };
  71.  
  72.  
  73. /* implementation of a persistent node */
  74.  
  75. class NODE
  76. {
  77.   friend class pers_rb_tree;
  78.  
  79.   void *key;
  80.   void *info;
  81.   NODE *parent;
  82.   int right;
  83.   int is_leaf;
  84.   F_NODE *link[2];
  85.   C_NODE *red;
  86.   F_NODE *copy;
  87.  
  88.   NODE* next;  // linking all used NODES
  89.  
  90.   OPERATOR_NEW(10)
  91.   OPERATOR_DEL(10)
  92. };
  93.  
  94. /* implementation of a node (or member) of the version list */
  95.  
  96. class VER_NODE
  97. { 
  98.   friend class pers_rb_tree;
  99.  
  100.   NODE*  acc_pointer;
  101.   int    popul;
  102.   double ser_num;
  103.  
  104.   OPERATOR_NEW(4)
  105.   OPERATOR_DEL(4)
  106. };
  107.  
  108. typedef VER_NODE* ver_node;
  109.  
  110. declare(list,ver_node);
  111.  
  112.  
  113. struct V_LIST {
  114.  
  115. list(ver_node) vl;
  116. int count;
  117. NODE* used;
  118.  
  119. };
  120.  
  121.  
  122.  
  123. class pers_rb_tree {
  124.  
  125. protected:
  126.  
  127. V_LIST* v_list;
  128.  
  129. virtual int cmp_keys(ent& x, ent& y) { return int(x)-int(y); }
  130. virtual void print_key(ent& x)       { Print(x); }
  131.  
  132. virtual void copy_key(ent& x)        { x=x; }
  133. virtual void copy_inf(ent& x)        { x=x; }
  134. virtual void clear_key(ent& x)       { x=0; }
  135. virtual void clear_inf(ent& x)       { x=0; }
  136.  
  137.  
  138. NODE* child(int leftright, NODE *p, version i)
  139. { return(acc_step(p->link[leftright], i)); }
  140.  
  141. void* get_key(NODE *p, version i)
  142. { return (acc_step(p->copy, i))->key; }
  143.  
  144. int isleaf(NODE *p) 
  145. { //return (p == p->link[0]->poin_value); 
  146.   return p->is_leaf;
  147.  }
  148.   
  149. NODE* sibling(NODE *p, version i)
  150. { return acc_step(p->parent->link[1 - p->right], i); } 
  151.  
  152.  
  153. /* define the order of versions in the version list */
  154. int vless(version x, version y)    
  155. { return  (v_list->vl[x]->ser_num < v_list->vl[y]->ser_num); }
  156.  
  157. /* find the next to a given version in the version list */ 
  158. version  iplus(version i)
  159. { return v_list->vl.succ(i); }
  160.  
  161.  
  162. NODE*   acc_step(F_NODE *, version);
  163. version new_version(version);
  164. void    m_b_root(version);
  165.  
  166. F_NODE* f_nleaf(NODE*, version);
  167. F_NODE* f_nnode(F_NODE*, F_NODE*);
  168. F_NODE* f_rbsearch(F_NODE* p, version);
  169. void    f_rbclear(F_NODE*);
  170. int     f_insert(F_NODE*, NODE*, version);
  171. void    f_single_rot(F_NODE*, int);
  172. void    f_double_rot(F_NODE*, int);
  173.  
  174. C_NODE* c_nleaf(int, version);
  175. C_NODE* c_nnode(C_NODE*, C_NODE*);
  176. C_NODE* c_rbsearch(C_NODE* p, version);
  177. void    c_rbclear(C_NODE*);
  178. int     c_insert(C_NODE*, int, version);
  179. void    c_single_rot(C_NODE*, int);
  180. void    c_double_rot(C_NODE*, int);
  181.  
  182. NODE*   single_rot(NODE* top_node, int dir, version i);
  183. NODE*   double_rot(NODE* top_node, int dir, version i);
  184. NODE*   newnode(NODE* c1, NODE* c2, version i);
  185. NODE*   newleaf(void* val, void* inf, NODE*, NODE*, version i);
  186. int     isred(NODE* p, version i);
  187. void    up_col(C_NODE* p, int newvalue, version i);
  188. void    update(F_NODE* p, NODE* newvalue, version i);
  189.  
  190. NODE*   search(void* val, version i)     { NODE* p; return search(val,p,i);}
  191. NODE*   search(void*, NODE*&, version);
  192.  
  193.  
  194. public:
  195.  
  196. // pers_rb_tree();
  197. //~pers_rb_tree();
  198.  
  199. void init_tree();
  200.  
  201. void* key(NODE* p)  { return p->key; }
  202. void* inf(NODE* p)  { return p->info; }
  203.  
  204. version del(void*, version);
  205. version insert(void*, void*, version);
  206. version change_inf(NODE*,void*,version);
  207.  
  208. NODE* lookup(void *val,version v);
  209. NODE* locate(void *val,version v);
  210. NODE* locate_pred(void *val,version v);
  211. NODE* min(version v);
  212. NODE* max(version v);
  213. NODE* succ(NODE* p, version v) { return child(1,p,v); }
  214. NODE* pred(NODE* p, version v) { return child(0,p,v); }
  215.  
  216. int   size(version v) { return v_list->vl[v]->popul; }
  217.  
  218. double ver_num(version v)  { return v_list->vl[v]->ser_num; }
  219.  
  220. void print(NODE*,version);
  221.  
  222. void del_tree();
  223.  
  224. void print(version v) 
  225. { //cout << form("%5f : ",v_list->vl[v]->ser_num);
  226.   print(v_list->vl[v]->acc_pointer,v);
  227.   newline;
  228.  }
  229.  
  230. void draw(DRAW_NODE_FCT,DRAW_EDGE_FCT, version, NODE*, double, double, double, double, double);
  231.  
  232. void draw(DRAW_NODE_FCT,DRAW_EDGE_FCT, version, double, double, double, double);
  233.  
  234. };
  235.  
  236.  
  237. #endif
  238.  
  239.